package com.test.daily.leetcode.y2022.m06.day0613.v05;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/6/13 下午 11:48
 * @version: 1.0
 */
public class Solution {
    public static int minSum(int[] arr){
        int N = arr.length;
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += arr[i];
        }
        sum /=2;
        if((N & 1) == 0){
            return process(arr, sum, 0,N/2);
        }else {
            return Math.min(process(arr, sum, 0,N/2), process(arr, sum, 0,N/2+1));
        }
    }
    public static int process(int[] arr, int rest,int index, int picks){
        if(index == arr.length){
            return rest == 0 ? 0: -1;
        }
        int p1 = process(arr, rest, index+1, picks);
        int p2 = -1;
        int next = -1;
        if(rest-arr[index] >= 0 && picks - 1 >= 0){
            next = process(arr, rest-arr[index], index+1, picks - 1);
        }
        if(next != -1){
            p2 = arr[index] + next;
        }
        return Math.max(p1, p2);
    }
}
